package string;

/**
 * 给你一个以二进制形式表示的数字 s 。请你返回按下述规则将其减少到 1 所需要的步骤数：
 * 如果当前数字为偶数，则将其除以 2 。
 * 如果当前数字为奇数，则将其加上 1 。
 * 题目保证你总是可以按上述规则将测试用例变为 1 。
 * <p>
 * 示例 1：
 * 输入：s = "1101"
 * 输出：6
 * 解释："1101" 表示十进制数 13 。
 * Step 1) 13 是奇数，加 1 得到 14
 * Step 2) 14 是偶数，除 2 得到 7
 * Step 3) 7  是奇数，加 1 得到 8
 * Step 4) 8  是偶数，除 2 得到 4
 * Step 5) 4  是偶数，除 2 得到 2
 * Step 6) 2  是偶数，除 2 得到 1
 * <p>
 * 示例 2：
 * 输入：s = "10"
 * 输出：1
 * 解释："10" 表示十进制数 2 。
 * Step 1) 2 是偶数，除 2 得到 1
 * <p>
 * 示例 3：
 * 输入：s = "1"
 * 输出：0
 *
 * @author Jisheng Huang
 * @version 20250503
 */
public class NumStepsToReduceToOne_1404 {

    public static int numSteps(String s) {
        // Base case
        if (s.length() == 0) {
            return 0;
        }

        int ans = 0;
        int carry = 0;

        for (int i = s.length() - 1; i >= 0; --i) {
            if (i == 0 && carry == 0) {
                break;
            }

            if (s.charAt(i) - '0' != carry) {
                carry = 1;
                ans += 1;
            }

            ans += 1;
        }

        return ans;
    }

    public static void main(String[] args) {
        String s = "1101";
        System.out.println(numSteps(s));

        s = "10";
        System.out.println(numSteps(s));

        s = "1";
        System.out.println(numSteps(s));
    }
}
